package arithmetic;

/**
 * 寻找最大正方形, 字节2
 * @author jiangfeng on 2022/3/16
 */
public class FinxMaxSquare {




        // 动态规划: 状态方程:  dp[i][j] = min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1] }+1
        public static int maxS(boolean[][] matrix){
            if(matrix== null ||matrix.length ==0 ||matrix[0].length == 0  ){
                return 0;
            }
            // dp[i][j] = min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1] }+1
            int[][] dp = new int[matrix.length][matrix[0].length];

            int maxSide = 0, cur = 0;
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[0].length; j++) {
                    cur = matrix[i][j] ? 1 : 0;
                    if (cur == 1) {
                        if (i == 0 || j == 0) {
                            dp[i][j] = cur;
                        } else {
                            dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        }
                        if (maxSide < dp[i][j]) {
                            maxSide = dp[i][j];
                        }

                    }
                }

            }
            //

            return maxSide*maxSide;
        }
}
